/**
 * https://leetcode-cn.com/problems/aMhZSa/
 * 判断是不是回文链表
 * @param head 
 */
const isPalindrome = (head: ListNode | null): boolean => {
    // 寻找中间节点 + 翻转链表
    // 边界判断
    if (head === null || head.next === null) return true;

    /**
     * 获取链表的中间节点
     * @param n 
     */
    const getMid = () => {
        // 快慢指针
        let slow = head,
            fast: ListNode | null = head;
        while (fast !== null && fast.next !== null) {
            slow = slow!.next
            fast = fast.next.next;

        }
        return slow
    }

    /**
     * 翻转链表
     * @param n 
     */
    const reverse = (n: ListNode | null) => {
        let newHead: ListNode | null = null

        while (n !== null) {
            const next: ListNode | null = n.next;
            n.next = newHead;
            newHead = n;
            n = next;
        }
        return newHead;
    }

    // 1. 获取中间节点
    let mid = getMid()

    // 2. 将中间节点进行翻转
    let reversedNode = reverse(mid);

    // 3. 进行比较
    while (reversedNode !== null && head !== null) {
        if (reversedNode.val !== head.val) return false;
        reversedNode = reversedNode.next;
        head = head.next;
    }

    return true;
};


// 利用数组
const isPalindrome2 = (head: ListNode | null): boolean => {
    // 边界判断
    if (head === null || head.next === null) return true;

    const arr: number[] = []

    // 遍历链表, 放入数组中
    while (head !== null) {
        arr.push(head.val);
        head = head.next;
    }

    // 头指针和尾指针
    let s = 0,
        e = arr.length - 1;


    while (s < e) {
        // 不是回文
        if (arr[s] !== arr[e]) return false
        s++;
        e--;
    }

    return true;
};

export {}